"""
排序算法实验模块（aboutsort.py）
提供直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序和归并排序的实现，并对每种排序进行了数据测试

Authors: 原盛（homework.xjtu@outlook.com）
Version: 1.0.0
Date: 2025-09-08

"""
import random
import matplotlib.pyplot as plt
import time
from enum import Enum
class SortingPattern(Enum):
    """
    SortingPattern是一个枚举类型，用来标记数据序列的分布状态，分三种形态：正序、逆序和随机（也就是均匀分布）
    """
    ASCENDING = 1     # 正序
    DESCENDING = 2    # 逆序
    RANDOM = 3        # 随机（均匀）

def generateData(volume, sort_pattern, repetition_rate):
    """
    生成数据序列：按照指定的序列的大小以及所包含的数据的重复率生成对应的数据序列
    Args:
        volume(int):定义生成的数据规模大小，应为整数，需满足 volume > 0
        sort_pattern(SortingPattern):声明待生成成数据序列的分布状态，只有当状态指定为SortingPattern.RANDOM时，才考虑数据的重复率（即参数repetition_rate）。
        repetition_rate: 指定数据序列的重复率，其值为[0,1]的小数，0代表完全不重复，1代表全部重复
    Returns:
        []: 返回一个数组，里面保存了按照要求生成的规模为volume的数据序列

    """
    data = [0]*volume
    match sort_pattern:
        case SortingPattern.RANDOM:
            data_set = volume - int(repetition_rate*volume) # 记录数据序列中互不相同的数据个数
            if data_set == 0:
                return data
            for i in range(data_set):
                data[i] = i
            start_index = data_set
            while start_index < volume:
                data[start_index] = random.randrange(0,data_set)
                start_index += 1
            random.shuffle(data) # 将数据随机打乱
        case SortingPattern.DESCENDING:
            for i in range(volume):
                data[i] = volume - i - 1
        case SortingPattern.ASCENDING:
            for i in range(volume):
                data[i] = i
    return data

def elapsedTime(function, array, tries):
    """
    计算函数function在规模volume上执行tries的平均运行时间
    Args:
        function:要运行的函数名称，该函数的形参要符合在elapsedTime函数中执行此函数的要求
        array(list): 函数function执行的数据集
        tries(int): 在给定的相同的volume上，函数function执行的次数，需满足tries>0
    Returns:
        float: 计算的运行时间大小
    Raises:
        RuntimeError: 当function执行周，数据集中的数据不是正序排序，那么要立即终止程序的运行
    """
    elapsed_time = 0.0
    origin_volume = array.copy()  # 因为函数function要在volume数据集上执行tries实验，为了保证公平，每次执行都应该有相同的数据
    for i in range(tries):
        start_time = time.time_ns()
        function(array)  # 本次实验中，function为不同的排序算法，故该算法中的参数内容即为要排序的数据集
        end_time = time.time_ns()
        if not is_sorted(array):
            raise RuntimeError('sorting failed')
        elapsed_time += end_time-start_time # 累加每调用一次function所花费的时间
        array = origin_volume.copy()
    return elapsed_time/tries

def sort_test(function, tries):
    """
    实现对function执行tries次运行测试的框架
    Args:
        function: 要运行的函数名称，该函数的形参要符合在elapsedTime函数中执行此函数的要求
        tries: 函数function的执行次数， 需满足tires>0
    Returns:
        (list, list):返回一个包含有两个数组的元组，其中第一个是存储不同大小的数据规模，第二个存储在对应规模下记录function的运行时间

    """
    volumes = [2 ** i for i in range(8, 16)]  # 生成了一组数据量
    elapsedtimes = []  # 用来记录对应数据量下的运行时间
    for volume in volumes:
        elapsed_time = elapsedTime(insert, generateData(volume, SortingPattern.RANDOM, 0), 1)
        elapsedtimes.append(elapsed_time)
    return (volumes, elapsedtimes)

def is_sorted(array):
    """
    用来判断array中记录的数据序列是否是正序序列
    Args:
        array(list): 存储已经排好序的数据
    Returns:
        bool: 如果array中的数据是正序序列，返回true，否则返回false
    """
    n = len(array)
    for i in range(n-1):
        if array[i] > array[i+1]:
            return False
    return True

# 最简洁的使用python绘制图表的方式，同学们可以自行查阅matplotlib的帮助文档，设置图例，设置图标标题，
# 更改颜色等都很容易完成
def show_chart(X, Y):
    """
    显示在给定的不同数量的数据集（X）上的运行时间（Y）的二维图形
    Args:
        X(list): 存储了做实验的数据量
        Y(list): 存储了X中对应的数据量下的函数的运行时间

    Returns: 无返回值
    """
    fig, ax = plt.subplots()
    ax.plot(X, Y)
    plt.show()

def insert(array):
    """
    在数据集上执行直接插入排序，使数据集成为正序序列的数据集
    Args:
        array(list): 记录了待排序的数据集
    Returns:
        None: 没有返回值
    """
    n = len(array)
    for i in range(1, n):
        temp = array[i]
        j = i
        while j > 0 and temp < array[j - 1]:
            array[j] = array[j - 1]
            j -= 1
        array[j] = temp

def main():
    (X,Y) = sort_test(insert, 1)
    show_chart(X, Y)


if __name__ == "__main__":
    main()